package com.leetcode.partition8;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/28 10:20
 */
public class LC790多米诺和托米诺平铺 {

    private static final int MOD = 1000000007;

    public static int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
        System.out.println(numTilings(1000));
    }

    private static int dynamicProgramming(int n) {
        //dp[i]：铺满2 * i地板有dp[i]种可能
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;
        //参考：https://leetcode-cn.com/problems/domino-and-tromino-tiling/solution/dong-tai-gui-hua-by-wpl-w-okdm/
        //dp[n]=dp[n-1]+dp[n-2]+(dp[0]+dp[1]+...+dp[n-3])*2
        //再结合dp[n-1]=dp[n-2]+dp[n-3]+(dp[0]+dp[1]+...+dp[n-4])*2，两式相减，得出dp[i]=2*dp[i-1]+dp[i-3]
        for (int i = 4; i <= n; i++) {
            dp[i] = ((2 * dp[i - 1]) % MOD + dp[i - 3]) % MOD;
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}
